package sorting;

import java.util.Arrays;

import util.ArrayUtil;
import util.MathUtil;

public class FuzzySort {
	public void sort(Interval[] intervals, int p, int s)
	{
		if(p == s)
			return;
		
		if(p - s > 1)
			ArrayUtil.each(intervals, s, MathUtil.random(p, s));
		
		Tag1 tag = partition(intervals, p, s);
		
		if(tag.getEl() > p)
			sort(intervals, p, tag.getEl() - 1);
		
		if(tag.getEr() < s)
			sort(intervals, tag.getEr() + 1, s);
	}

	private Tag1 partition(Interval[] intervals, int p, int s)
	{
		Interval v = new Interval(intervals[s].getBegin(), intervals[s].getEnd());
		int q = p;
		int r = s;
		int i = p;
		while(i <= r)
		{
			Interval interval = intervals[i];
			
			if(interval.getEnd() < v.getBegin())
			{
				ArrayUtil.each(intervals, i ++, q ++);
			}
			else if(interval.getBegin() > v.getEnd())
			{
				ArrayUtil.each(intervals, i, r --);
			}
			else
			{
				v.setBegin(Math.max(v.getBegin(), interval.getBegin()));
				v.setEnd(Math.min(v.getEnd(), interval.getEnd()));
				i ++;
			}
		}

		return new Tag1(q, r);
	}
	
	public static void main(String[] args) {
		Interval[] intervals = new Interval[]{
				new Interval(1, 1.5f),
				new Interval(1, 3),
				new Interval(5, 8),
				new Interval(3, 5),
				new Interval(3, 4),
				new Interval(2, 4),
				new Interval(2, 3)
		};
		
		new FuzzySort().sort(intervals, 0, intervals.length - 1);
		System.out.println(Arrays.deepToString(intervals));
	}
}

class Tag1
{
	private int el;
	private int er;
	public Tag1(int el, int er) {
		this.el = el;
		this.er = er;
	}
	
	public int getEl() {
		return el;
	}
	
	public int getEr() {
		return er;
	}
}

